{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Concatenation of Consecutive Binary Numbers"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #bit-manipulation #math #simulation"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #位运算 #数学 #模拟"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: concatenatedBinary"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #连接连续二进制数字"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个整数 <code>n</code> ，请你将 <code>1</code> 到 <code>n</code> 的二进制表示连接起来，并返回连接结果对应的 <strong>十进制</strong> 数字对 <code>10<sup>9</sup> + 7</code> 取余的结果。</p>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre><b>输入：</b>n = 1\n",
    "<b>输出：</b>1\n",
    "<strong>解释：</strong>二进制的 \"1\" 对应着十进制的 1 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><b>输入：</b>n = 3\n",
    "<b>输出：</b>27\n",
    "<strong>解释：</strong>二进制下，1，2 和 3 分别对应 \"1\" ，\"10\" 和 \"11\" 。\n",
    "将它们依次连接，我们得到 \"11011\" ，对应着十进制的 27 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre><b>输入：</b>n = 12\n",
    "<b>输出：</b>505379714\n",
    "<b>解释：</b>连接结果为 \"1101110010111011110001001101010111100\" 。\n",
    "对应的十进制数字为 118505380540 。\n",
    "对 10<sup>9</sup> + 7 取余后，结果为 505379714 。\n",
    "</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= n &lt;= 10<sup>5</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [concatenation-of-consecutive-binary-numbers](https://leetcode.cn/problems/concatenation-of-consecutive-binary-numbers/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [concatenation-of-consecutive-binary-numbers](https://leetcode.cn/problems/concatenation-of-consecutive-binary-numbers/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['1', '3', '12']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def concatenatedBinary(self, n: int) -> int:\n",
    "        #相当于从前往后算，比如12是二进制的四位，所以拼接完12的二进制再回来十进制就是前面的所有数乘2^4。而二进制位数可以通过2的多少次方大于这个数来得到。\n",
    "        result = 0\n",
    "        weishu = 1   #记录二进制中的位数\n",
    "        for i in range(n):\n",
    "            temp = i+1\n",
    "            if 2**weishu == temp:\n",
    "                weishu += 1\n",
    "            result = (result*2**weishu + temp) % (10**9+7)\n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def concatenatedBinary(self, n: int) -> int:\n",
    "        exp = 1\n",
    "        res = 1\n",
    "        for i in range(2, n+1):\n",
    "            if i==2**exp:\n",
    "                exp += 1\n",
    "            res = ((res<<exp) | i)%1000000007\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def concatenatedBinary(self, n: int) -> int:\n",
    "        mod = 10 ** 9 + 7\n",
    "        ans = 0\n",
    "        for i in range(1, n+1):\n",
    "            size = i.bit_length()\n",
    "            ans = ((ans<<size) +i) % mod\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def concatenatedBinary(self, n: int) -> int:\n",
    "        ret = 0\n",
    "        M = 10 ** 9 + 7\n",
    "        \n",
    "        def qpow(a, x):\n",
    "            ret = 1\n",
    "            while x:\n",
    "                if x & 1:\n",
    "                    ret = ret * a % M\n",
    "                x >>= 1\n",
    "                a = a * a % M\n",
    "            return ret\n",
    "        \n",
    "        for i in range(1, n + 1):\n",
    "            cnt = 0\n",
    "            tmp = i\n",
    "            while tmp:\n",
    "                cnt += 1\n",
    "                tmp >>= 1\n",
    "            ret = (ret * qpow(2, cnt) + i) % M            \n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def concatenatedBinary(self, n: int) -> int:\n",
    "        \n",
    "        # def turn2(num):\n",
    "        #     res = ''\n",
    "        #     while num >= 2:\n",
    "        #         remain = num % 2\n",
    "        #         num //= 2\n",
    "        #         res = str(remain) + res\n",
    "        #     res = str(num) + res\n",
    "        #     return res\n",
    "\n",
    "        # def turn10(str_num):\n",
    "        #     res = 0\n",
    "        #     n = len(str_num)\n",
    "        #     for i,x in enumerate(str_num):\n",
    "        #         if int(x):\n",
    "        #             res += 2**(n-i-1)\n",
    "        #     return res\n",
    "            \n",
    "        # tmp = ''\n",
    "        # for i in range(1,n+1):\n",
    "        #     tmp += turn2(i)\n",
    "        # ans = turn10(tmp)\n",
    "        # return ans%(10**9+ 7)\n",
    "\n",
    "        # return int(''.join([bin(j)[2:] for j in range(1,n+1)]),2)%(10**9+7)\n",
    "\n",
    "        ans = 0\n",
    "        mod = 10**9 + 7\n",
    "        for k in range(1, len(bin(n))-1):\n",
    "            for cur in range(1<<(k-1), 1<<k):\n",
    "                ans = ((ans<<k)+cur)%mod\n",
    "                if cur == n:\n",
    "                    return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD = 10**9+7\n",
    "class Solution:\n",
    "    def concatenatedBinary(self, n: int) -> int:\n",
    "        t = 1\n",
    "        for i in range(2,n+1):\n",
    "            k = len(bin(i))-2\n",
    "            t = (t<<k)|i\n",
    "            t = t%MOD\n",
    "        return int(t%(MOD))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def concatenatedBinary(self, n: int) -> int:\n",
    "        mod = 10**9+7\n",
    "        ans = 0\n",
    "        for i in range(n+1):\n",
    "            ans = ((ans<<i.bit_length())+i)%mod\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def concatenatedBinary(self, n: int) -> int:\n",
    "        # MOD = 10 ** 9 + 7\n",
    "        # ans = 0\n",
    "        # posi = 0\n",
    "        # for i in range(n, 0, -1):\n",
    "        #     chs = bin(i)[2:][::-1]\n",
    "        #     for ch in chs:\n",
    "        #         if ch == '1':\n",
    "        #             ans += (1 << posi)\n",
    "        #             # ans %= MOD\n",
    "        #         posi += 1\n",
    "        # return ans % MOD\n",
    "\n",
    "\n",
    "        MOD = 10 ** 9 + 7\n",
    "        ans = shift = 0\n",
    "        for i in range(1, n+1):\n",
    "            if i & (i - 1) == 0:\n",
    "                shift += 1\n",
    "            ans = ((ans << shift) + i) % MOD\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def concatenatedBinary(self, n: int) -> int:\n",
    "        mod = 10**9 + 7\n",
    "        # # ans 表示答案，shift 表示 len_{2}(i)\n",
    "        ans = shift = 0\n",
    "        for i in range(1, n + 1):\n",
    "            # if 131072 % i == 0:\n",
    "            if (i & (i - 1)) == 0:\n",
    "                shift += 1\n",
    "            ans = ((ans << shift) + i) % mod\n",
    "        # ans = 12 ** 12\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD = 10 ** 9 + 7\n",
    "class Solution:\n",
    "    def concatenatedBinary(self, n: int) -> int:\n",
    "        x = 0\n",
    "        for i in range(1, n + 1):\n",
    "            x = ((x << i.bit_length()) + i) % MOD\n",
    "        return x"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def concatenatedBinary(self, n: int) -> int:\n",
    "        res, shift = 0, 0\n",
    "        MOD = 10 ** 9 + 7\n",
    "        for i in range(1, n + 1):\n",
    "            if (i & (i -1)) == 0:\n",
    "                shift += 1\n",
    "            res = ((res << shift) + i) % MOD\n",
    "        return res\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def concatenatedBinary(self, n: int) -> int:\n",
    "        # 模拟\n",
    "        # mod = 10**9 + 7\n",
    "        # # ans 表示答案，shift 表示 len_{2}(i)\n",
    "        # ans = shift = 0\n",
    "        # for i in range(1, n + 1):\n",
    "        #     # if 131072 % i == 0:\n",
    "        #     if (i & (i - 1)) == 0:\n",
    "        #         shift += 1\n",
    "        #     ans = ((ans << shift) + i) % mod\n",
    "        # return ans\n",
    "        \n",
    "        # 数学\n",
    "        mod = 10**9 + 7\n",
    "        zeroes = 0\n",
    "        ans = 0\n",
    "        for k in range(64, 1, -1):   # 任意 64 位无符号整数都可以秒出答案\n",
    "            if (lb := 2 ** (k - 1)) <= n:\n",
    "                t = n - lb\n",
    "                u = pow(2, t * k, mod)\n",
    "                v = pow(2 ** k - 1, mod - 2, mod)\n",
    "                w = pow(2, (t + 1) * k, mod)\n",
    "                x = pow(2, zeroes, mod)\n",
    "                ans += (2 ** k * (u - 1) * v + (n - t) * w - n) * v * x % mod\n",
    "                zeroes += (t + 1) * k\n",
    "                n = lb - 1\n",
    "        \n",
    "        ans += pow(2, zeroes, mod)\n",
    "        return ans % mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def concatenatedBinary(self, n: int) -> int:\n",
    "        mod = 10**9 + 7\n",
    "        # ans 表示答案，shift 表示 len_{2}(i)\n",
    "        ans = shift = 0\n",
    "        for i in range(1, n + 1):\n",
    "            # if 131072 % i == 0:\n",
    "            if (i & (i - 1)) == 0:\n",
    "                shift += 1\n",
    "            ans = ((ans << shift) + i) % mod\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def concatenatedBinary(self, n: int) -> int:\n",
    "        mod = 10**9 + 7\n",
    "        zeroes = 0\n",
    "        ans = 0\n",
    "        for k in range(64, 1, -1):   # 任意 64 位无符号整数都可以秒出答案\n",
    "            if (lb := 2 ** (k - 1)) <= n:\n",
    "                t = n - lb\n",
    "                u = pow(2, t * k, mod)\n",
    "                v = pow(2 ** k - 1, mod - 2, mod)\n",
    "                w = pow(2, (t + 1) * k, mod)\n",
    "                x = pow(2, zeroes, mod)\n",
    "                ans += (2 ** k * (u - 1) * v + (n - t) * w - n) * v * x % mod\n",
    "                zeroes += (t + 1) * k\n",
    "                n = lb - 1\n",
    "        \n",
    "        ans += pow(2, zeroes, mod)\n",
    "        return ans % mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def concatenatedBinary(self, n: int) -> int:\n",
    "        mod = 10 ** 9 + 7\n",
    "        ans = 0\n",
    "        size = 0\n",
    "        for i in range(1, n+1):\n",
    "            # size = i.bit_length()\n",
    "            if i & (i-1) == 0:\n",
    "                size += 1\n",
    "            ans = ((ans<<size) +i) % mod\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def concatenatedBinary(self, n: int) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        ans = 0\n",
    "        for i in range(1, n + 1):\n",
    "            s = i.bit_length()\n",
    "            ans = (ans << s) | i\n",
    "            ans %= MOD\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def concatenatedBinary(self, n: int) -> int:\n",
    "        mod = 10**9 + 7\n",
    "        ans = 0\n",
    "        shift = 1\n",
    "        pre = 1\n",
    "        for i in range(1, n + 1):\n",
    "            if i >= 2 * pre:\n",
    "                shift += 1\n",
    "                pre = 2 * pre\n",
    "            ans = ((ans << shift) + i) % mod\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def concatenatedBinary(self, n: int) -> int:\n",
    "        res = 0\n",
    "        wei = 0\n",
    "        two = 0\n",
    "        mod = 10**9 + 7\n",
    "\n",
    "        for i in range(1,n+1):\n",
    "            if i & (i-1)==0:\n",
    "                wei+=1\n",
    "            \n",
    "            res=((res<<wei)+i)%mod\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def concatenatedBinary(self, n: int) -> int:\n",
    "        s = 0\n",
    "        for i in range(1, n+1):\n",
    "            l = len(bin(i))-2\n",
    "            s = s<<l\n",
    "            s = (s % (10**9 + 7) + i % (10**9 + 7))% (10**9 + 7)\n",
    "        return s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def concatenatedBinary(self, n: int) -> int:\n",
    "        result, m = 1, 10 ** 9 + 7\n",
    "        for i in range(2, n+1):\n",
    "            k = i.bit_length()\n",
    "            result = ((result << k) % m + i) % m\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD = 10 ** 9 + 7\n",
    "\n",
    "class Solution:\n",
    "    def concatenatedBinary(self, n: int) -> int:\n",
    "        x = 0\n",
    "        for i in range(1, n + 1):\n",
    "            x = (x << i.bit_length()) % MOD + i\n",
    "        return x"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def concatenatedBinary(self, n: int) -> int:\n",
    "        ans = 0\n",
    "        MOD = 10 ** 9 + 7\n",
    "        for x in range(1, n + 1):\n",
    "            ans = (ans << self.bit_len(x)) + x\n",
    "            ans %= MOD\n",
    "        return ans\n",
    "    \n",
    "    def bit_len(self, n: int) -> int:\n",
    "        cnt = 0\n",
    "        while n:\n",
    "            cnt += 1\n",
    "            n >>= 1\n",
    "        return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def concatenatedBinary(self, n: int) -> int:\n",
    "        # return int(''.join([str(bin(i+1))[2:] for i in range(n)]), 2) % (pow(10, 9) + 7)\n",
    "        ans = 0\n",
    "        mod = 10**9+7\n",
    "        for k in range(1,len(bin(n))-1): #外循环枚举位数\n",
    "            for cur in range(1<<(k-1),1<<k): #内循环枚举所有二进制表示为k位的整数\n",
    "                ans=((ans<<k)+cur)%mod \n",
    "                if cur==n:\n",
    "                    return ans #及时返回答案"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def concatenatedBinary(self, n: int) -> int:\n",
    "        res = 0\n",
    "        shift=0\n",
    "        for i in range(1, n+1):\n",
    "            if not (i&(i-1)):shift+=1\n",
    "            res = ((res << shift)|i) % 1_000_000_007\n",
    "        return res\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def concatenatedBinary(self, n: int) -> int:\n",
    "        mod = int(1e9 + 7)\n",
    "\n",
    "        sum_ = 0\n",
    "        for i in range(1, n + 1):\n",
    "            sum_ <<= len(bin(i)) - 2\n",
    "            sum_ %= mod\n",
    "            sum_ += i\n",
    "            sum_ %= mod\n",
    "        return sum_"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def concatenatedBinary(self, n: int) -> int:\n",
    "        if n == 1:\n",
    "            return 1\n",
    "\n",
    "        ans = size = 0\n",
    "        for i in range(1, n+1):\n",
    "            ans = (ans << self.lenBinary(i)) + i\n",
    "            size += self.lenBinary(i)\n",
    "            ans %= (10 ** 9 + 7)\n",
    "\n",
    "        return ans\n",
    "\n",
    "    def lenBinary(self, x):\n",
    "        return x.bit_length()\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def concatenatedBinary(self, n: int) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        res = 0\n",
    "        for i in range(1, n+1):\n",
    "            k = len(bin(i)[2:])\n",
    "            res = ((res << k) % MOD + i) % MOD\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def concatenatedBinary(self, n: int) -> int:\n",
    "        s=\"\"\n",
    "        e=0\n",
    "        for x in range(1,n+1):\n",
    "           e=(e*2**(len(str(bin(x)))-2)+x)%(10**9+7)\n",
    "        return e    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def concatenatedBinary(self, n: int) -> int:\n",
    "        s=\"\"\n",
    "        e=0\n",
    "        ans=0\n",
    "        k=0\n",
    "        for x in range(1,n+1):\n",
    "           if x&(x-1)==0:\n",
    "               k+=1\n",
    "           ans=((ans<<k)+x)%(10**9+7)    \n",
    "        return ans    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def concatenatedBinary(self, n: int) -> int:\n",
    "        mod = 10**9 + 7\n",
    "        zeroes = 0\n",
    "        ans = 0\n",
    "        for k in range(64, 1, -1):   # 任意 64 位无符号整数都可以秒出答案\n",
    "            if (lb := 2 ** (k - 1)) <= n:\n",
    "                t = n - lb\n",
    "                u = pow(2, t * k, mod)\n",
    "                v = pow(2 ** k - 1, mod - 2, mod)\n",
    "                w = pow(2, (t + 1) * k, mod)\n",
    "                x = pow(2, zeroes, mod)\n",
    "                ans += (2 ** k * (u - 1) * v + (n - t) * w - n) * v * x % mod\n",
    "                zeroes += (t + 1) * k\n",
    "                n = lb - 1\n",
    "        \n",
    "        ans += pow(2, zeroes, mod)\n",
    "        return ans % mod\n",
    "\n",
    "    # def concatenatedBinary(self, n: int) -> int:\n",
    "    #     res = 0\n",
    "    #     shift=0\n",
    "    #     for i in range(1, n+1):\n",
    "    #         if not (i&(i-1)):shift+=1\n",
    "    #         res = ((res << shift)|i) % 1_000_000_007\n",
    "    #     return res\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def concatenatedBinary(self, n: int) -> int:\n",
    "        MOD = 10**9 + 7\n",
    "        result = 0\n",
    "        length = 0\n",
    "        \n",
    "        for i in range(1, n+1):\n",
    "            # 如果i是2的幂，则长度增加\n",
    "            if (i & (i - 1)) == 0:\n",
    "                length += 1\n",
    "            # 将结果左移相应的长度并添加当前的数字\n",
    "            result = ((result << length) + i) % MOD\n",
    "        \n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def concatenatedBinary(self, n: int) -> int:\n",
    "        s = ''\n",
    "        for i in range(1,n+1):\n",
    "            s += bin(i)[2:]\n",
    "        return int(s,base=2)%(10**9+7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def concatenatedBinary(self, n: int) -> int:\n",
    "        s = \"\"\n",
    "        i = 1\n",
    "        for i in range(n+1):\n",
    "            s = s + bin(i)[2:]\n",
    "        x = int(s, 2)\n",
    "        x = x % (10 **9 + 7)\n",
    "        return x"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def concatenatedBinary(self, n: int) -> int:\n",
    "        res = \"\"\n",
    "        for i in range(1, n+1):\n",
    "            res += bin(i)[2:]\n",
    "        return int(res, 2) % (10 ** 9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def concatenatedBinary(self, n: int) -> int:\n",
    "        s = ''\n",
    "        for i in range(1,n+1):\n",
    "            s += bin(i)[2:]\n",
    "            # print(bin(i),bin(i)[2:])\n",
    "        # print(s)\n",
    "        return int(s,2)%(10**9+7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def concatenatedBinary(self, n: int) -> int:\n",
    "        s = ''\n",
    "        for i in range(1,n+1):\n",
    "            s += bin(i)[2:]\n",
    "        return int(s,base=2)%(7+10**9)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def concatenatedBinary(self, n: int) -> int:\n",
    "        ans = \"\"\n",
    "        for i in range(1, n + 1) :\n",
    "            ans += str(bin(i))[2:]\n",
    "        return int(ans, 2) % (10 **9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def concatenatedBinary(self, n: int) -> int:\n",
    "        ans = \"\"\n",
    "        for i in range(1, n + 1) :\n",
    "            ans += str(bin(i))[2:]\n",
    "        return int(ans, 2) % (10 **9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "MOD = 10**9+7\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def concatenatedBinary(self, n: int) -> int:\n",
    "        lst = [1]\n",
    "        for i in range(2, n+1):\n",
    "            cur = len(bin(i))-2\n",
    "            lst.append((lst[-1]*(1 << cur)+i)%MOD)\n",
    "\n",
    "        return lst[n-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "dp = []\n",
    "n = 10**5\n",
    "mod = 10**9 + 7\n",
    "ans = 0\n",
    "for x in range(1, n+1):\n",
    "    for w in bin(x)[2:]:\n",
    "        ans = 2*ans + int(w)\n",
    "        ans %= mod\n",
    "    dp.append(ans)\n",
    "    \n",
    "class Solution:\n",
    "    def concatenatedBinary(self, n: int) -> int:\n",
    "        return dp[n-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "N = 10 ** 5\n",
    "s = ''\n",
    "for x in range(1, N + 1):\n",
    "    s += str(bin(x)[2:])\n",
    "\n",
    "class Solution:\n",
    "    def concatenatedBinary(self, n: int) -> int:\n",
    "        cnt = len(bin(n)[2:])\n",
    "        start = 0\n",
    "        for i in range(cnt):\n",
    "            tmp = pow(2, i+1) - pow(2, i)\n",
    "            start += (i+1) * tmp\n",
    "        return int(s[:start - (pow(2, cnt) - n - 1) * cnt], 2) % (10 ** 9 + 7)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "N = 10 ** 5\n",
    "s = ''\n",
    "for x in range(1, N + 1):\n",
    "    s += str(bin(x)[2:])\n",
    "cnt = len(bin(N)[2:])\n",
    "end = [0] * (cnt + 1)\n",
    "for i in range(cnt):\n",
    "    tmp = pow(2, i+1) - pow(2, i)\n",
    "    end[i] += end[i-1] + (i+1) * tmp\n",
    "class Solution:\n",
    "    def concatenatedBinary(self, n: int) -> int:\n",
    "        m = len(bin(n)[2:])\n",
    "        return int(s[:end[m-1] - (pow(2, m) - n - 1) * m], 2) % (10 ** 9 + 7)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import binascii\n",
    "class Solution:\n",
    "    def concatenatedBinary(self, n: int) -> int:\n",
    "        res_str = ''\n",
    "        for i in range(1, n+1):\n",
    "            a = str(bin(i))\n",
    "            res_str += a[2:]\n",
    "        \n",
    "        s1 = bytes(res_str, encoding='utf-8')\n",
    "        num1 = int(s1, 2)\n",
    "        return num1 % 1000000007"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def concatenatedBinary(self, n: int) -> int:\n",
    "        return int(''.join([bin(j)[2:] for j in range(1,n+1)]),2)%(10**9+7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def concatenatedBinary(self, n: int) -> int:\n",
    "        \n",
    "        # def turn2(num):\n",
    "        #     res = ''\n",
    "        #     while num >= 2:\n",
    "        #         remain = num % 2\n",
    "        #         num //= 2\n",
    "        #         res = str(remain) + res\n",
    "        #     res = str(num) + res\n",
    "        #     return res\n",
    "\n",
    "        # def turn10(str_num):\n",
    "        #     res = 0\n",
    "        #     n = len(str_num)\n",
    "        #     for i,x in enumerate(str_num):\n",
    "        #         if int(x):\n",
    "        #             res += 2**(n-i-1)\n",
    "        #     return res\n",
    "            \n",
    "        # tmp = ''\n",
    "        # for i in range(1,n+1):\n",
    "        #     tmp += turn2(i)\n",
    "        # ans = turn10(tmp)\n",
    "        # return ans%(10**9+ 7)\n",
    "\n",
    "        return int(''.join([bin(j)[2:] for j in range(1,n+1)]),2)%(10**9+7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def concatenatedBinary(self, n: int) -> int:\n",
    "        return int(''.join([bin(i)[2:] for i in range(1,n+1)]),2)%int(1e9+7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def concatenatedBinary(self, n: int) -> int:\n",
    "        return int(\"\".join(bin(i+1)[2:] for i in range(n)), 2) % (10 **9 + 7)\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
